package com.yayako.main.struc;

import java.util.*;

/**
 * DFA类
 *
 * @author cyy
 */
public class DFA {
    /** 初态 */
    private final int s0;
    /** 终态集合 */
    private LinkedHashSet<Integer> f;
    /** dfa图 */
    private Digraph digraph;
    /** 对应的nfa */
    private NFA nfa;
    /** 对应的正规式 */
    private String regex;

    public DFA(NFA nfa) {
        this.nfa = nfa;
        regex = nfa.getRegex();
        s0 = nfa.getS0();
        digraph = new Digraph();
        // 记录nfa状态的转移闭包，即每一次smove的结果
        HashMap<String, List<Integer>> closure = new HashMap<>();
        f = new LinkedHashSet<>();
        // 使用map记录所有的dfa闭包，保持唯一
        LinkedHashMap<List<Integer>, Integer // 最低位记录该list是否已被访问，其他位记录该状态集对应的dfa状态
                >
                set = new LinkedHashMap<>();
        // 初态的空闭包
        List<Integer> initTrans = smove(0, 'ε', closure);
        initTrans.add(0);
        set.put(initTrans, 0);
        digraph.addVertex(initTrans);

        int i = -1; // 代表当前正在进行转移的状态列表
        int num = 0; // 记录dfa状态总数
        List<Integer> list;

        HashSet<Character> cSet = getNormalChar();
        // 遍历所有dfa状态的状态集
        for (int k = 0; k < set.size(); ++k) {
            try {
                for (List<Integer> statesList : set.keySet()) {
                    // 最低位为1，代表已被访问
                    if ((set.get(statesList) & 1) == 1) {
                        continue;
                    }
                    ++i;
                    // 遍历所有的非分隔字符
                    for (char c : cSet) {
                        List<Integer> tmp = new ArrayList<>();
                        // 遍历nfa状态
                        for (Integer stateOfNFA : statesList) {
                            // 包含nfa终态，则该闭包为dfa的终态之一
                            if (stateOfNFA == nfa.getF()) {
                                f.add(i);
                                digraph.getVertex(i).setFinal();
                            }
                            // 获得nfa状态转移闭包
                            list = smove(stateOfNFA, c, closure);
                            if (list.size() > 0) {
                                tmp.addAll(list);
                            }
                        }
                        // 求得闭包为空
                        if (tmp.size() == 0) {
                            digraph.addEdge(i, -1, c);
                            continue;
                        }
                        // 非重复的闭包
                        if (!set.containsKey(tmp)) {
                            // 增加节点
                            digraph.addVertex(tmp);
                            set.put(tmp, (++num << 1));
                        }
                        // 连接两节点
                        digraph.addEdge(i, set.get(tmp) >>> 1, c);
                    }
                    // 修改状态为已访问
                    set.put(statesList, set.get(statesList) | 1);
                }
            } catch (ConcurrentModificationException ignored) {
            }
        }
    }

    String getRegex() {
        return regex;
    }

    @Override
    public String toString() {
        return "\nDFA:\n"
                + "regex = \""
                + regex
                + '\"'
                + "\ns0 = "
                + s0
                + ", f = "
                + f
                + ",\nmove = {"
                + digraph
                + "\n}\n";
    }

    Digraph getGraph() {
        return digraph;
    }

    HashSet<Character> getNormalChar() {
        HashSet<Character> set = new HashSet<>();
        for (char c : regex.toCharArray()) {
            if (c != '*' && c != '|' && c != '(' && c != ')' && c != 'ε') {
                set.add(c);
            }
        }
        return set;
    }

    private List<Integer> smove(int state, char in, HashMap<String, List<Integer>> closure) {
        List<Integer> list = closure.get(String.valueOf(state) + in);
        if (list != null) {
            return list;
        }

        // 输入 in 的直通状态集
        list = nfa.getDigraph().nextVertex(state, in);
        // 空闭包
        int n = list.size();
        for (int i = 0; i < n; ++i) {
            list.addAll(smove(list.get(i), 'ε', closure));
        }

        closure.put(String.valueOf(state) + in, list);
        return list;
    }
}
